//
package AVLTree;
import java.util.List;
import java.util.LinkedList;
import java.util.Comparator;


/**
 * @author Waseem
 * @version 1.0
 * @param <T>
 */
public class AVLTree<T extends Comparable<T>> implements BSTInterface<T>{

	/**
	 * 
	 */
	public Node<T> root;
	
	/**
	 * 
	 */
	private int size = 0;
	
	/**
	 * 
	 */
	private final Comparator<T> comp = new Comparator<T >() {
		public int compare(T item, T other){
			if(item == other){
				return 0;
			}
			else if(item == null){
				return 1;
			}
			else if(other == null){
				return -1;
			}
			else{
				return item.compareTo(other);
			}
		}
	};
	
	/* (non-Javadoc)
	 * @see AVLTree.BSTInterface#add(java.lang.Comparable)
	 */
	@Override
	public void add(T data) {
		if(root == null){
			final Node<T> node = new Node<T>(data);
			root = node;
			calcHeightAndBF(root);
			size++;
		}
		else{
			if(get(data) == null){
				root = add(root, data);
				size++;
			}
		}	
	}
	
	/**
	 * @param curr
	 * @param item
	 * @return
	 */
	private Node<T> add ( Node <T > curr, T item ){	
		if(curr != null){
			if(comp.compare(curr.getData(), item) == 1){
				curr.setLeft(add(curr.getLeft(), item));
			}
			else{
				curr.setRight(add(curr.getRight(), item));
			}
		}
		else{
			curr = new Node<T>(item);
		}
		
		calcHeightAndBF(curr);
		return rotate(curr);		
	}
	
	/* (non-Javadoc)
	 * @see AVLTree.BSTInterface#remove(java.lang.Comparable)
	 */
	@Override
	public T remove(T data) {
		final Node<T> ans = new Node<T>(null);
		root = remove(root, data, ans);
		
		if(comp.compare(ans.getData(), data) == 0){
			size--;
		}
				
		return ans.getData();
	}
	
	/**
	 * @param node
	 * @param data
	 * @param temp
	 * @return
	 */
	private Node<T> remove(Node<T> node, T data, Node<T> temp){
		if(node == null){
			temp.setData(null);
			return null;
		}
		
		if(comp.compare(node.getData(), data) == 0){
			temp.setData(node.getData());
			if(node.getLeft() == null && node.getRight() == null){
				return null;
			}	
			else if(node.getLeft() == null && node.getRight() != null){
				return node.getRight();
			}
			else if(node.getLeft() != null && node.getRight() == null){
				return node.getLeft();
			}
			else{
				node.setRight(succ(node.getRight(), node));
				if(node != null){
					calcHeightAndBF(node);
					node = rotate(node);
				}
				
				return node;
			}
		}	
		else{
			if(comp.compare(node.getData(), data) == 1){
				temp.setData(node.getData());
				node.setLeft(remove(node.getLeft(), data, temp));
			}
			else{
				temp.setData(node.getData());
				node.setRight(remove(node.getRight(), data, temp));
			}
			
			calcHeightAndBF(node);
			node = rotate(node);
		}
		
		return node;
	}
	
	/**
	 * @param node
	 * @param target
	 * @return
	 */
	@SuppressWarnings("unused")
	private Node<T> pred(Node<T> node, Node<T> target){
		if(node.getRight() == null) {
			target.setData(node.getData());
			node = node.getLeft();
		}
		else {
			node.setRight(pred(node.getRight(), target));
			calcHeightAndBF(node);
			rotate(node);
		}
		
		return node;
	}
	
	/**
	 * @param node
	 * @param target
	 * @return
	 */
	private Node<T> succ(Node<T> node, Node<T> target) {
		if(node.getLeft() == null) {
			target.setData(node.getData());
			node = node.getRight();
		}
		else {
			node.setLeft(succ(node.getLeft(), target));
			calcHeightAndBF(node);
			rotate(node);
		}
		
		return node;
	}

	/* (non-Javadoc)
	 * @see AVLTree.BSTInterface#clear()
	 */
	@Override
	public void clear() {
		root = null;
		size = 0;
	}

	/* (non-Javadoc)
	 * @see AVLTree.BSTInterface#isEmpty()
	 */
	@Override
	public boolean isEmpty() {
		return size == 0;
	}

	/* (non-Javadoc)
	 * @see AVLTree.BSTInterface#get(java.lang.Comparable)
	 */
	@Override
	public T get(T data) {
		Node<T> node = root;
		
		while(node != null) {
			if(comp.compare(node.getData(), data) == 1) {
				node = node.getLeft();
			}
			else if(comp.compare(node.getData(), data) == -1) {
				node = node.getRight();
			}
			else {
				return node.getData();
			}
		}
		
		return null;
	}

	/* (non-Javadoc)
	 * @see AVLTree.BSTInterface#asSortedList()
	 */
	@Override
	public List<T> asSortedList() {
		return inOrder(root, new LinkedList<T>());
	}
	
	/**
	 * @param curr
	 * @param list
	 * @return
	 */
	private List<T> inOrder(Node<T> curr, List<T> list) {	
		if(curr != null) {
			inOrder(curr.getLeft(), list);
			list.add(curr.getData());
			inOrder(curr.getRight(), list);
		}
		
		return list;
	}

	/* (non-Javadoc)
	 * @see AVLTree.BSTInterface#size()
	 */
	@Override
	public int size() {
		return size;
	}
	
	/**
	 * @param n
	 */
	public void calcHeightAndBF(Node<T> n) {
		final int heightLeft = (n.getLeft() == null ) ? -1 : n.getLeft().getHeight();
		final int heightRight = (n.getRight() == null) ? -1 : n.getRight().getHeight();
		
		n.setHeight(Math.max(heightLeft, heightRight) + 1);
		n.setBf(heightLeft - heightRight);
	}
	
	/**
	 * @param n
	 * @return
	 */
	public Node<T> left(Node<T> n) {
		final Node<T> node = new Node<T>(n.getRight().getData());
		node.setRight(n.getRight().getRight());
		n.setRight(n.getRight().getLeft());
		node.setLeft(n);
		
		calcHeightAndBF(node.getLeft());
		calcHeightAndBF(node);
		
		return node;
	}
	
	/**
	 * @param n
	 * @return
	 */
	public Node<T> right(Node<T> n) {
		final Node<T> node = new Node<T>(n.getLeft().getData());
		node.setLeft(n.getLeft().getLeft());
		n.setLeft(n.getLeft().getRight());
		node.setRight(n);
		
		calcHeightAndBF(node.getRight());
		calcHeightAndBF(node);
		
		return node;
	}
	
	/**
	 * @param n
	 * @return
	 */
	public Node<T> leftRight(Node<T> n) {
		n.setLeft(left(n.getLeft()));
		return right(n);
	}
	
	/**
	 * @return
	 */
	public Node<T> getRoot() {
		return root;
	}
	
	/**
	 * @param n
	 * @return
	 */
	public Node<T> rightLeft(Node<T> n) {
		n.setRight(right(n.getRight()));
		return left(n);
	}
	
	/**
	 * @param n
	 * @return
	 */
	public Node<T> rotate(Node<T> n) {
		if(n.getBf() <= -2 && n.getRight().getBf() > 0) {
			//System.out.println("right left");
			return rightLeft(n);
		}
		else if(n.getBf() >= 2 && n.getLeft().getBf() < 0) {
			//System.out.println("left right");
			return leftRight(n);
		}
		else if(n.getBf() <= -2) {
			//System.out.println("left");
			return left(n);
		}
		else if(n.getBf() >= 2) {
			//System.out.println("right");
			return right(n);
		}
		else {
			return n;
		}
		
	}
	
	/* (non-Javadoc)
	 * @see java.lang.Object#toString()
	 */
	@Override
	public String toString() {
		return super.toString();
	}
	
	
		
//	public static void main(String[] args)
//	{
//		AVLTree<Integer> tree = new AVLTree<Integer>();		
////		tree.add(7);
////		tree.add(4);
////		tree.add(5);
////		tree.add(6);
////		tree.add(15);
////		tree.remove(7);
////		tree.add(9);
////		tree.add(54);
////		tree.add(89);
////		tree.add(23);
////		tree.add(78);
////		tree.add(65);
////		tree.remove(54);
////		tree.remove(15);
////		tree.remove(78);
////		tree.remove(23);
////		tree.remove(5);
////		tree.remove(4);
////		tree.remove(6);
////		tree.remove(65);
////		tree.remove(9);
////		tree.remove(7);
////		tree.remove(8);
////		tree.remove(0);
////		tree.remove(89);
//
////		tree.add(1);
////		tree.add(2);
////		tree.add(3);
////		tree.add(4);
////		tree.add(5);
////		tree.add(6);
//		
//		//tree.add(3);
//		//tree.add(2);
//		tree.add(5);
//		tree.add(3);
//		tree.add(6);
//		
//		AVLTree<Integer> f = new AVLTree<Integer>();
//		f.add(3);
//		f.add(2);
//		f.add(1); 
//		f.add(4);
//		f.add(5);
//		f.add(6);
//		f.add(7);
//		f.add(16);
//		f.add(15);
//		f.add(14);
//		f.remove(1);
//		f.remove(3);
//			
//		System.out.println(f.root.getRight().getData());
//		//System.out.println(tree.root.getHeight());
//	}
}